package leecode;

import org.junit.Test;

/**
 * @Classname BinarySearch
 * @Description TODO
 * @Date 2021/7/27 17:28
 * @Created by Alberthch
 */
public class Solution_0_BinarySearch {



    /**
     *     // 将数组分成三段：low~mid-1  mid  mid+1~high
     *     // 当查找的target一定在数组arr中时，能返回正确的下标
     *     // 若不在arr中，返回的是  arr[i]<= target < arr[i+1]  中的i，即所夹位置的较小一个数的下标
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch_1(int[] arr,int target) {
        int n = arr.length;
        if (n == 0 ){
            return -1;
        }

        int low = 0;
        int high = n-1;
        int mid;
        while (low < high) {
            mid = (high-low)/2 + low;
            if (arr[mid] == target) {
                return mid;
            }else if (arr[mid] < target) {
                low = mid +1;
            } else {
                high = mid-1;
            }
        }

        return low;
    }

    @Test
    public void testbinarySearch_1(){
        int[] arr = {0,2,4,4,8,10};
        System.out.println("方法1：");
        System.out.println(binarySearch_1(arr,6));
        System.out.println(binarySearch_1(arr,5));
    }


    /**
     *     // 将数组分成三段：low~mid-1  mid  mid+1~high
     *     // 当查找的target一定在数组arr中时，能返回正确的下标
     *     // 若不在arr中，返回的是  arr[i]<= target < arr[i+1]  中的i，即所夹位置的较小一个数的下标
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch_2(int[] arr,int target) {
        int n = arr.length;
        if (n == 0 ){
            return -1;
        }

        int low = 0;
        int high = n-1;
        int mid;
        while (low < high) {
            mid = (high-low)/2 + low;
            if (arr[mid] == target) {
                return mid;
            }else if (target < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }

    @Test
    public void testbinarySearch_2(){
        int[] arr = {0,2,4,4,8,10};
        // 可用写法
        System.out.println("方法2：");
        System.out.println(binarySearch_2(arr,6));
        System.out.println(binarySearch_2(arr,5));
    }


    /**
     *    // 将数组分成两段：low~mid  mid+1~high
     *     // 当查找的target一定在数组arr中时，能返回正确的下标
     *     // 若不在arr中，返回的是  arr[i-1]< target <= arr[i]  中的i，即所夹位置的较大一个数的下标
     * @param arr     待搜索数组
     * @param target  搜索目标
     * @return
     */
    public static int binarySearch_3(int[] arr,int target) {
        int n = arr.length;
        if (n == 0 ){
            return -1;
        }

        int low = 0;
        int high = n-1;
        int mid;
        while (low < high) {
            mid = (high-low)/2 + low;
            if (arr[mid] < target) {
                low = mid+1;
            } else {
                high = mid;
            }
        }

        return low;
    }

    @Test
    public void testbinarySearch_3(){
        int[] arr = {0,2,4,4,8,10};

        // 最推荐使用方法3，可以得到正确的位置，以及所夹元素中的较大元素下标，一般先判断在右边区域，对low首先赋值
        // 需要的到所夹元素的较小元素小标，推荐使用方法1，对low进行先判断
        System.out.println("方法3：");
        System.out.println(binarySearch_3(arr,0));
        System.out.println(binarySearch_3(arr,1));
        System.out.println(binarySearch_3(arr,2));
        System.out.println(binarySearch_3(arr,3));
        System.out.println(binarySearch_3(arr,4));

        System.out.println(binarySearch_3(arr,9));
        System.out.println(binarySearch_3(arr,10));
        System.out.println(binarySearch_3(arr,11));
    }


    /**
     *     // 将数组分成三段：low~mid  mid+1~high
     *     // 当查找的target一定在数组arr中时，不能返回正确的下标
     *     // 若不在arr中，返回的是  arr[i]< target < arr[i+1]  中的i，即所夹位置的较小一个数的下标
     *     // 该方法不能用
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch_4(int[] arr,int target) {
        int n = arr.length;
        if (n == 0 ){
            return -1;
        }

        int low = 0;
        int high = n-1;
        int mid;
        while (low < high) {
            mid = (high-low)/2 + low;
            if (target < arr[mid]) {
                high = mid;
            } else {
                low = mid+1;
            }
        }

        return low;
    }

    @Test
    public void testbinarySearch_4() {
        int[] arr = {0,2,4,4,8,10};

        // 错误的写法
        System.out.println("方法4：");
        System.out.println(binarySearch_4(arr,6));
        System.out.println(binarySearch_4(arr,5));
    }
}
